package 笔试.网易;

import java.util.ArrayList;

/**
 * @author:谢君臣
 * @Date:2021/8/21-15:04
 * @version:1.0
 * @function: [[1, 1, 1, 1, 0], [0, 1, 0, 1, 0], [1, 1, 2, 1, 1], [0, 2, 0, 0, 1]]
 */
public class Main04 {
    public static void main(String[] args) {
        System.out.println(Solution(new int[][]{{1, 1, 1, 1, 0}, {0, 1, 0, 1, 0}, {1, 1, 2, 1, 1}, {0, 2, 0, 0, 1}}));
    }

    public static int minSailCost(int[][] input) {
        // write code here
        if (input[input.length - 1][input[0].length - 1] == 2)
            return -1;
        return findPath(input, 0, 0, 0);
    }

    private static int findPath(int[][] input, int i, int j, int num) {
        if (i == input.length - 1 && j == input[0].length - 1) {
            return num;
        } else {
            input[i][j] = 2;
            int top = -1, bottom = -1, left = -1, right = -1;
            if (i - 1 >= 0 && input[i - 1][j] != 2)
                top = findPath(arrayCopy(input), i - 1, j, num + get(input[i - 1][j]));
            if (i + 1 < input.length && input[i + 1][j] != 2)
                bottom = findPath(arrayCopy(input), i + 1, j, num + get(input[i + 1][j]));
            if (j - 1 >= 0 && input[i][j - 1] != 2)
                left = findPath(arrayCopy(input), i, j - 1, num + get(input[i][j - 1]));
            if (j + 1 < input[0].length && input[i][j + 1] != 2)
                right = findPath(arrayCopy(input), i, j + 1, num + get(input[i][j+1]));
            if (top < 0 && bottom < 0 && left < 0 && right < 0)
                return -1;
            else {
                ArrayList<Integer> arrayList = new ArrayList<>();
                if (top >= 0) arrayList.add(top);
                if (bottom >= 0) arrayList.add(bottom);
                if (left >= 0) arrayList.add(left);
                if (right >= 0) arrayList.add(right);
                arrayList.sort(Integer::compareTo);
                return arrayList.get(0);
            }
        }
    }
    public static int get(int k){
        if (k==0) return 2;
        else return 1;
    }

    public static int[][] arrayCopy(int[][] input) {
        int[][] res = new int[input.length][input[0].length];
        for (int i = 0; i < input.length; i++)
            for (int j = 0; j < input[0].length; j++)
                res[i][j] = input[i][j];
        return res;
    }

    public static int Solution(int[][] input) {
        int l = input.length, r = input[0].length;
        int[][] dp = new int[l][r];
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                dp[i][j] = Integer.MAX_VALUE-10;
            }
        }
        dp[0][0] = 0;
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                if (i - 1 >= 0 && input[i - 1][j] != 2){
                    int temp = dp[i - 1][j] + get(input[i][j]);
                    dp[i][j] = Math.min(temp, dp[i][j]);}
                if (i + 1 < l && input[i + 1][j] != 2){
                    int temp = dp[i + 1][j] + get(input[i][j]);
                    dp[i][j] = Math.min(temp, dp[i][j]);
                }
                if (j - 1 >= 0 && input[i][j - 1] != 2) dp[i][j] = Math.min(dp[i][j - 1] + get(input[i][j]), dp[i][j]);
                if (j + 1 < r && input[i][j + 1] != 2) dp[i][j] = Math.min(dp[i][j + 1] + get(input[i][j]), dp[i][j]);
            }
        }
        System.out.println(dp[l - 1][r - 1]);
        return dp[l - 1][r - 1];
    }


}
